Service providers and device manufacturers (e.g., wireless, cellular, etc.) are continually challenged to deliver value and convenience to consumers by, for example, providing compelling network services. One area of interest has been the development of personal information management (PIM) services and functions (e.g., calendar, contacts, tasks, etc.), particularly for use in mobile devices (e.g.; smartphones, cell phones, portable computers, etc.). For example, equipped with relatively powerful processors and fairly large memory and storage capabilities, such mobile devices can accommodate an increasing number of interactive applications that act on sensitive PIM-related data. The growing amount of sensitive information shared by mobile device users raises privacy concerns. Accordingly, service providers and device manufacturers face significant technical challenges to enabling privacy-preserving mechanisms when dealing with such information. For example, mobile device users have access to context-based services (e.g., social networking, dating, activity-partner searching, etc.) that often involve determining common availabilities for scheduling appointments (e.g., meetings) among the multiple users. In this case, privacy of the scheduling operation can be a concern to users, particularly when such services are provided by third parties or involve users who do not have previously established trust relationships.